package com.example.design.leetcode.list;

//剑指 Offer 52. 两个链表的第一个公共节点
//
//        输入两个链表，找出它们的第一个公共节点。
//        如下面的两个链表：
//        a1->a2->c1->c2->c3
//        b1->b2->b3->c1->c2->c3
//        在节点 c1 开始相交。
//
//        输出：c1

//    注意：
//    如果两个链表没有交点，返回 null.
//    在返回结果后，两个链表仍须保持原有的结构。
//    可假定整个链表结构中没有循环。
//    程序尽量满足 O(n) 时间复杂度，且仅用 O(1) 内存。
//    本题与主站 160 题相同：https://leetcode-cn.com/problems/intersection-of-two-linked-lists/

//        标签：双指针链表遍历
public class Practice31 {

    ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode curA = headA;
        ListNode curB = headB;

        while(curA != curB) {
            curA = curA != null ? curA.next:headB;
            curB = curB != null ? curB.next:headA;
        }

        return curA;
    }


    ListNode getIntersectionNode2(ListNode headA, ListNode headB) {
        ListNode curA = headA;
        ListNode curB = headB;

        while(curA != curB) {
            curA = curA != null ? curA.next: headB;
            curB = curB != null ? curB.next: headA;
        }

        return curA;
    }


}
